Electrical Engineering-Systems Dept.

סמינר מחלקתי

You are invited to attend a lecture by

Prof. Guy Even

(Electrical Engineering School,Tel Aviv University)

on the subject:

Analysis of LP-decoding and message passing decoding using local optimality

We presents a unified analysis framework that capturesrecent advances in the study of local-optimality characterizationsfor codes on graphs. These local-optimality characterizations arebased on combinatorial structures embedded in the Tanner graph of the code. Local-optimality implies both maximum-likelihood (ML) optimality and linear-programming (LP) decoding optimality. Also, aniterative message-passing decoding algorithm is guaranteed to findthe unique locally-optimal codeword, if one exists.

This proof technique is demonstrated by considering a definition oflocal optimality that is based on the simplest combinatorialstructures in Tanner graphs, namely, paths of length h. Guarantees forsuccessful decoding are obtained even when h exceeds the girth of theTanner graph.

We will also discuss more advanced characterizations of local optimality that are based on skinny trees and d-trees in thecomputation tree.

Joint work with Nissim Halabi.